6.20 Reductions

We proved that \(A_\mathrm{TM}\) is undecidable using a tricky proof by contradiction. If we want to prove that other languages are undecidable, we can try to find similar tricks. But a simpler strategy is to leverage what we have already proved, a method known as reduction.

Definition

Given problems \(P\) and \(Q\), we say that \(P\) reduces to \(Q\), written \[ P \leq Q \] if a solution to \(Q\) would let us solve \(P\) as well.

The notation is odd at first glance. The best way to think about \(P \leq Q\) is that it refers to difficulty; \(P\) is easier (or at least, no harder) than \(Q\) if solving \(Q\) also tells us how to solve \(P\).

Not surprisingly, any formal language that is harder to decide than an undecidable language is also undecidable.

Example

The language \[ \mathit{HALT} = \{\ \langle M,w\rangle\ |\ M \mathrm{~halts~on~input~} w\ \} \] is semidecidable, but not decidable.

Proof of Semidecidability: To show that \(\mathit{HALT}\) is semidecidable, we can just give the algorithm for a semidecider, namely:

def semidecide_Halt(M, w):
simulate(M, w)
return True

That is, a semidecider for \(\mathit{HALT}\) can simulate the given machine on the given input. If this halts then (whether it accepts or rejects) the semidecider accepts the pair. If the machine runs forever on that input, the semidecider returns no answer. > Proof of Undecidability: We will show that \(A_\mathrm{TM} \leq \mathit{HALT}\), i.e. that if we could decide \(\mathit{HALT}\) then we could decide \(A_\mathrm{TM}\). Since we know \(A_\mathrm{TM}\) is not decidable, it follows that \(\mathit{HALT}\) is not decidable either. > In other words, as soon as we prove that \(\mathit{HALT}\) is at least as hard as the undecidable \(A_\mathrm{TM}\), we know that \(\mathit{HALT}\) is undecidable too. > Here is why \(A_\mathrm{TM} \leq \mathit{HALT}\): > Suppose we could build a decider decide_Halt for \(\mathit{HALT}\). > Then we could build a decider decide_Atm for \(A_\mathrm{TM}\) as follows: > >>def decide_Atm(M, w): > if decide_Halt(M, w): > return simulate(M, w) > else: > return False > > That is, to correctly predict whether \(M\) will accept \(w\), we first check whether \(M\) will halt on \(w\). If so, we can run \(M\) on \(w\) and be sure we will see it accept or reject in a finite amount of time. If not, we know \(M\) does not accept \(w\) and can report that immediately.

Proving Reductions

Decidability Reduction Proofs (\(L_1\leq L_2\))

What does a proof look like?

Assume there is a decider for \(L_2\).
[Show an algorithm for deciding \(L_1\).]
Therefore \(L_1\) reduces to \(L_2\). QED.

The direction is important. We assume the right-hand-side is decidable, and show that, if so, the left-hand-side is decidable.

Why is this useful?

This direction is easiest to prove, but the logically equivalent contrapositive is more useful, namely

This means that if we do a reduction proof where \(L_1\) is a language like \(A_\mathrm{TM}\) that we already know is not decidable, then our reduction proof guarantees that \(L_2\) is not decidable.

For example, in the example above we proved that \(A_\mathrm{TM} \leq \mathit{HALT}\) (i.e., if \(A_\mathrm{TM}\) is not decidable, then \(\mathit{HALT}\) is not decidable). It immediately follows that \(\mathit{HALT}\) is not decidable. So then if we manage to prove \(\mathit{HALT}\leq L'\) for some other language \(L'\), it will immediately follow that \(L'\) is not decidable either. In this way, we can use reduction to prove that more and more languages are not decidable.

Example

\[ A\mathrm{prime} := \{\ \langle M,w\rangle\ | \ M\mathrm{~accepts~} w \mathrm{~\&~} M\mathrm{'s~code~has~a~prime~number~of~states}\ \} \] We can show \(A\mathrm{prime}\) is undecidable by proving \(A_\mathrm{TM} \leq A\mathrm{prime}\).

Proof 1
>Suppose there were a decider decide_Aprime for \(A\mathrm{prime}\). Then we could decide \(A_\mathrm{TM}\) as follows: > >Suppose we want to know if \(\langle M,w\rangle\in A_\mathrm{TM}\). > >We can’t just run decide_Aprime on \(M\) and \(w\). If the answer is “yes” then we would know that \(M\) accepts \(w\) (and has a prime number of states). But if the answer is “no” it might be because \(M\) doesn’t accept \(w\) or because \(M\) has a non-prime number of states or both; we get no information. > >1. Construct a TM \(M'\) that is exactly like \(M\) plus enough extra dummy/unreachable/useless states so that it has a prime number of states. > We haven’t changed the essential functionality of the TM, so \(L(M) = L(M')\), and \(M\) accepts \(w\) iff \(M'\) accepts \(w\). > >2. We can run decide_Aprime on \(M'\) and \(w\) to find out whether \(M'\) accepts \(w\) and has a prime number of states. > >3. Since \(M'\) has a prime number of states by construction, the result (true or false) tells us whether \(M'\) accepts \(w\), and hence whether \(M\) accepts \(w\). > Proof 2
Suppose there were a decider decide_Aprime for \(A\mathrm{prime}\). Then we could decide \(A_\mathrm{TM}\) as follows: > >Suppose we want to know if \(\langle M,w\rangle\in A_\mathrm{TM}\). > >1. Let \(n\) be the number of states in \(M\). > >2. Construct TMs \(M_0, M_1, \ldots, M_n\) such that \(M_i\) is just like \(M\) but with \(i\) extra dummy/unreachable states. > >3. A bit of number theory (for any \(n\geq 1\), there is a prime number between \(n\) and \(2n\)) guarantees that at least one of the \(M_i\)’s has a prime number of states. > >4. Run decide_Aprime on \(M_i\) and \(w\) for all \(i\in 0..n\). > >5. If at least one answer is “yes” then \(M\) accepts \(w\). Otherwise, \(M\) does not accept \(w\). > >This is like the first proof, but instead of deciding ahead of time how many states to get prime number of states, we just try a finite number of different possibilities knowing that at least one of them makes the total number of states prime and forces decide_Aprime to give us accurate information about whether \(M\) accepts \(w\).

Semidecidability Reduction Proofs (\(L_1\leq L_2\))

What does a proof look like?

A typical semidecidability reduction proof that \(L_1\leq L_2\) goes as follows:

Assume there is a semidecider for \(L_2\).
[Show an algorithm for semideciding \(L_1\).]
Therefore \(L_1\) reduces to \(L_2\). QED. #### Why is this useful?

This means that if we do a reduction proof where \(L_1\) is a language like \(\lnot A_\mathrm{TM}\) that we already know is not semidecidable, then our reduction proof guarantees that \(L_2\) is not semidecidable.

What’s up with the notation?

Irritatingly, the notation \(L_1\leq L_2\) and terminology “\(L_1\) reduces to \(L_2\)” can either mean “if \(L_2\) is decidable then so is \(L_1\)” or “if \(L_2\) is semidecidable then so is \(L_1\),” and these are not equivalent statements. Context usually tells us which meaning is intended.